Union Find 백준 1717 집합의 표현 문제 설명 입력이 0 1 2라고 주어지면 1이 포함된 집합과 2가 포함된 집합 합치기 입력이 1 2 3라고 주어지면 2, 3이 같은 집합이면 YES 아니라면 NO 출력 문제 풀이 집합에 포함이 된다? → 같은 부모로 묶여있다. → Union-find 골드 문제에 정답 비율도 낮아서 단순히 union-find로 풀면 시간초과나 놓친 반례가 있을 것이라 생각했는데 그냥 맞았다...ㅎㅎ 소스 코드... Union FindalgorithmUnion Find 백준 2162번: 선분 그룹 선분이 교차하면 Union. 유니온 파인드 자료구조에서 p[root]에는 원소의 개수(음수로) 저장. 여기서 둘 다 자세하게 설명했으니 따로 적진 않겠다. 알아야 하는 개념이 좀 많다. 실전에서 이런거 문제로 나오면 시간없어서 못풀듯..... Union FindDisjointSetgeometrycpppsDisjointSet 백준 3197번: 백조의 호수 문명 문제랑 완전 똑같다. 문명이 퍼지는 대신 물이 퍼진다. 퍼질때마다 상하좌우 확인해서 물 있으면 Union, 연도 바뀌면 find. 사실 year가 아니라 day긴 함 ㅋㅋ; 맨 처음에 물이랑 백조 싹다 큐에 넣으면서 상하좌우에 물이나 백조 있으면 Union 해준다. 이거 정답률이 19퍼인데 다들 bfs dfs만 들이박다 시간초과가 나온 듯 하다.... Union FindpsBFScppDisjointSetBFS 백준 17398번: 통신망 분할 완성 상태에서 하나씩 끊어보면서 찾으면 10만 * 10만이라 풀 수 없다. 맨 처음에, 제거될 예정인 연결은 빼고 union한다. 그리고 입력받은 역순으로 연결하면서 비용을 더해준다. 비용이 int 범위를 넘어갈 수 있기 때문에 long long으로 선언해야한다. 이런 디테일이 부족한 것 같다.... Union FindDisjointSetpscppDisjointSet 우주신과의 교감_1774번 황선자씨는 우주신과 교감을 할수 있는 채널러 이다. 하지만 우주신은 하나만 있는 것이 아니기때문에 황선자 씨는 매번 여럿의 우주신과 교감하느라 힘이 든다. 하지만 위대한 우주신들은 바로 황선자씨와 연결될 필요가 없다. 이미 황선자씨와 혹은 이미 우주신끼리 교감할 수 있는 우주신들이 있기 때문에 새로운 우주신들은 그 우주신들을 거쳐서 황선자 씨와 교감을 할 수 있다. 우주신들과의 교감은 우주신... Union Find그래프 이론최소 스패닝 트리Union Find 백준 11085번: 군사 이동 C랑 V랑 연결시키는데 이 때 연결한 길의 w중 최소가 가장 큰 경우를 구하려고 한다. 즉 빙빙 돌아가도 상관 없으니 한번에 군사를 많이 이동하려면 어떻게 해야하는가? 를 묻는 문제다. 간선을 w순으로 정렬하고 w가 큰 간선부터 union 연산을 한다. 종료조건은 find(C) == find(V). 가장 최근 연결했던 간선의 w를 출력하면 정답! 문제 뭔소린지 이해 안돼서 한참 읽었다. 난 ... Union FindDisjointSetpscppDisjointSet [BOJ 4195] 친구 네트워크 (Java) 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오. 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. 첫째 줄에 테스트 케이스의 개수가... Union Find해시Union Find [BOJ 10775] 공항 (Python) 처음에는 비행기를 중심으로 1번 ~ 입력받는 gi번 사이의 모든 게이트를 탐색하여 그중 비어있는 게이트에 비행기를 도킹시키려고 하였다. 시간복잡도는 O(GP)로 100,000 x 100,000 = 10,000,000,000 시간초과를 예상하였고, 다른 방법으로 풀려하였다. 비행기를 도킹할 때 항상 도킹할 수 있는 가장 큰 수의 게이트에 도킹해야한다. 왜냐하면 최대 도킹 수를 구해야하기 때문이... Union Findbojdisjoint set자료구조알고리즘Union Find 백준 1717번 집합의 표현 출처 : 저는 이 문제를 파이썬의 딕셔너리 자료형을 이용해서 풀었습니다. info_dic을 통해서 각 숫자가 들어가 있는 집합의 index를 저장 set_dic을 통해서 각 set_dic[index]의 집합을 리스트로 저장 주어진 연산에 따라서 조건문을 통해서 구현 조건은 순서대로 다음과 같다. a, b 가 둘다 정해진 집합이 없을 때 a는 정해진 집합이 없고 b는 정해진 집합이 있을 때 b... 백준코테Union Find알고리즘Union Find 백준 1043 거짓말 이 문제는 지민이가 과장된 이야기를 할 수 있는 파티의 갯수를 구하는 문제이다. 이 때 지민이의 이야기의 진실을 알고 있는 사람이 주어지고 각 파티에 어떤 사람들이 오는지가 번호로 주어진다. 이 문제를 풀기 위해서는 결국 진실을 알고 있는 사람이 속한 파티들을 제외한 파티의 갯수가 답이 되게 된다. 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 과장... Union Find백준분리집합Union Find [백준] 여행 가자(1976) 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라... Union Find백준Javabackjoon자바알고리즘Java [알고리즘] 백준 1043 거짓말 상당히 고생했던 문제이다. 유니온 파인드라는 알고리즘을 알지 못해서 해결방법을 떠올리지 못했다. 개요 진실을 알고 있는 사람들과 같은 파티에 있는 사람들은 모두 진실을 알고 있는 사람들과 같게 된다. 풀이 처음에는 거짓말 할 수 있는 파티를 1, 없는 파티를 0으로 두어 모든 경우의 수를 탐색하려 했다. 그러니 시간 복잡도가 O(2^n)이 되어 버려 n<50인 이번 문제를 해결하지 못한다. ... 알고리즘Union FindCC
백준 1717 집합의 표현 문제 설명 입력이 0 1 2라고 주어지면 1이 포함된 집합과 2가 포함된 집합 합치기 입력이 1 2 3라고 주어지면 2, 3이 같은 집합이면 YES 아니라면 NO 출력 문제 풀이 집합에 포함이 된다? → 같은 부모로 묶여있다. → Union-find 골드 문제에 정답 비율도 낮아서 단순히 union-find로 풀면 시간초과나 놓친 반례가 있을 것이라 생각했는데 그냥 맞았다...ㅎㅎ 소스 코드... Union FindalgorithmUnion Find 백준 2162번: 선분 그룹 선분이 교차하면 Union. 유니온 파인드 자료구조에서 p[root]에는 원소의 개수(음수로) 저장. 여기서 둘 다 자세하게 설명했으니 따로 적진 않겠다. 알아야 하는 개념이 좀 많다. 실전에서 이런거 문제로 나오면 시간없어서 못풀듯..... Union FindDisjointSetgeometrycpppsDisjointSet 백준 3197번: 백조의 호수 문명 문제랑 완전 똑같다. 문명이 퍼지는 대신 물이 퍼진다. 퍼질때마다 상하좌우 확인해서 물 있으면 Union, 연도 바뀌면 find. 사실 year가 아니라 day긴 함 ㅋㅋ; 맨 처음에 물이랑 백조 싹다 큐에 넣으면서 상하좌우에 물이나 백조 있으면 Union 해준다. 이거 정답률이 19퍼인데 다들 bfs dfs만 들이박다 시간초과가 나온 듯 하다.... Union FindpsBFScppDisjointSetBFS 백준 17398번: 통신망 분할 완성 상태에서 하나씩 끊어보면서 찾으면 10만 * 10만이라 풀 수 없다. 맨 처음에, 제거될 예정인 연결은 빼고 union한다. 그리고 입력받은 역순으로 연결하면서 비용을 더해준다. 비용이 int 범위를 넘어갈 수 있기 때문에 long long으로 선언해야한다. 이런 디테일이 부족한 것 같다.... Union FindDisjointSetpscppDisjointSet 우주신과의 교감_1774번 황선자씨는 우주신과 교감을 할수 있는 채널러 이다. 하지만 우주신은 하나만 있는 것이 아니기때문에 황선자 씨는 매번 여럿의 우주신과 교감하느라 힘이 든다. 하지만 위대한 우주신들은 바로 황선자씨와 연결될 필요가 없다. 이미 황선자씨와 혹은 이미 우주신끼리 교감할 수 있는 우주신들이 있기 때문에 새로운 우주신들은 그 우주신들을 거쳐서 황선자 씨와 교감을 할 수 있다. 우주신들과의 교감은 우주신... Union Find그래프 이론최소 스패닝 트리Union Find 백준 11085번: 군사 이동 C랑 V랑 연결시키는데 이 때 연결한 길의 w중 최소가 가장 큰 경우를 구하려고 한다. 즉 빙빙 돌아가도 상관 없으니 한번에 군사를 많이 이동하려면 어떻게 해야하는가? 를 묻는 문제다. 간선을 w순으로 정렬하고 w가 큰 간선부터 union 연산을 한다. 종료조건은 find(C) == find(V). 가장 최근 연결했던 간선의 w를 출력하면 정답! 문제 뭔소린지 이해 안돼서 한참 읽었다. 난 ... Union FindDisjointSetpscppDisjointSet [BOJ 4195] 친구 네트워크 (Java) 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오. 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. 첫째 줄에 테스트 케이스의 개수가... Union Find해시Union Find [BOJ 10775] 공항 (Python) 처음에는 비행기를 중심으로 1번 ~ 입력받는 gi번 사이의 모든 게이트를 탐색하여 그중 비어있는 게이트에 비행기를 도킹시키려고 하였다. 시간복잡도는 O(GP)로 100,000 x 100,000 = 10,000,000,000 시간초과를 예상하였고, 다른 방법으로 풀려하였다. 비행기를 도킹할 때 항상 도킹할 수 있는 가장 큰 수의 게이트에 도킹해야한다. 왜냐하면 최대 도킹 수를 구해야하기 때문이... Union Findbojdisjoint set자료구조알고리즘Union Find 백준 1717번 집합의 표현 출처 : 저는 이 문제를 파이썬의 딕셔너리 자료형을 이용해서 풀었습니다. info_dic을 통해서 각 숫자가 들어가 있는 집합의 index를 저장 set_dic을 통해서 각 set_dic[index]의 집합을 리스트로 저장 주어진 연산에 따라서 조건문을 통해서 구현 조건은 순서대로 다음과 같다. a, b 가 둘다 정해진 집합이 없을 때 a는 정해진 집합이 없고 b는 정해진 집합이 있을 때 b... 백준코테Union Find알고리즘Union Find 백준 1043 거짓말 이 문제는 지민이가 과장된 이야기를 할 수 있는 파티의 갯수를 구하는 문제이다. 이 때 지민이의 이야기의 진실을 알고 있는 사람이 주어지고 각 파티에 어떤 사람들이 오는지가 번호로 주어진다. 이 문제를 풀기 위해서는 결국 진실을 알고 있는 사람이 속한 파티들을 제외한 파티의 갯수가 답이 되게 된다. 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 과장... Union Find백준분리집합Union Find [백준] 여행 가자(1976) 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라... Union Find백준Javabackjoon자바알고리즘Java [알고리즘] 백준 1043 거짓말 상당히 고생했던 문제이다. 유니온 파인드라는 알고리즘을 알지 못해서 해결방법을 떠올리지 못했다. 개요 진실을 알고 있는 사람들과 같은 파티에 있는 사람들은 모두 진실을 알고 있는 사람들과 같게 된다. 풀이 처음에는 거짓말 할 수 있는 파티를 1, 없는 파티를 0으로 두어 모든 경우의 수를 탐색하려 했다. 그러니 시간 복잡도가 O(2^n)이 되어 버려 n<50인 이번 문제를 해결하지 못한다. ... 알고리즘Union FindCC